import java.util.Stack;

/**
 * @author wangj881
 * @date 2024-12-10 18:45
 */
public class L20_2 {
    public static void main(String[] args) {
        boolean valid = new Solution().isValid("()[]{}");
        System.out.println(valid);
    }

    static class Solution {
        public boolean isValid(String s) {
            Stack<Character> stack = new Stack<>();
            for (char ca : s.toCharArray()) {
                if (ca == '(' || ca == '[' || ca == '{') {
                    stack.push(ca);
                }
                if (ca == ')') {
                    if (stack.size() == 0 || stack.peek() != '(') {
                        return false;
                    } else {
                        stack.pop();
                    }
                }
                if (ca == ']') {
                    if (stack.size() == 0 || stack.peek() != '[') {
                        return false;
                    } else {
                        stack.pop();
                    }
                }
                if (ca == '}') {
                    if (stack.size() == 0 || stack.peek() != '{') {
                        return false;
                    } else {
                        stack.pop();
                    }
                }
            }
            return stack.size() == 0;
        }
    }
}
